Das Vorlesungsverzeichnis enthält die Belegnummer und offizielle Kommentare zur Vorlesung. Für die Übungen gibt es einen separaten Eintrag. Die Veranstaltung ist dem Modul Ausgewählte Kapitel der Algorithmik zugeordnet.

• 22.1.2014: das achte Übungsblatt ist online.
• 21.1.2014: die neue Version des Skripts und Folien sind online.
• 16.1.2014: das siebte Übungsblatt und die neue Version des Skripts sind online.
• 9.1.2014: die neue Version des Skripts ist online.

In dieser Vorlesung beschäftigen wir uns mit dem Problem, einen (oft sehr langen) Text so vorzuverarbeiten, dass im Anschluss effiziente Suchanfragen darin ausgeführt werden können. Beispiele solcher Anfragen reichen von einfachen Pattern-Matching Anfragen (“kommt ein Suchmuster im Text vor?”) bis hin zu komplexen Data-Mining-Anfragen, z.B. die Suche nach repetitiven Mustern. Im einzelnen behandeln wir die folgenden Themen:

• Textindizes: Suffixbäume, Suffix-Arrays, Suffix-Trays, Inverted Indexes
• exakte und approximative Mustersuche mit Hilfe von Textindizes
• Funktionalität von Suchmaschinen: schnelle Berechnung und Sortierung aller Dokumente, die ein Suchmuster enthalten
• Textkompression: Burrows-Wheeler-Transformation und LZ-Komprimierung

Sie sollten Spaß an algorithmischen Problem und der Analyse von Algorithmen haben. Die Vorlesungen DAP1 und DAP2 sollten nicht zu Ihren schlechtesten Fächern gehört haben. Im Idealfall haben Sie bereits andere Veranstaltungen aus diesem Bereich gehört (Algorithmen und Datenstrukturen, Effiziente Algorithmen, Algorithm Engineering, Algorithmische Bioinformatik, etc.) bzw. haben vor, dies noch zu tun.

Für die Übungen sind Programmierkenntnisse in C/C++ oder Java erforderlich.

Die Vorlesung ist geeignet für Informatiker im Master- oder Diplomstudiengang (Hauptstudium). Sie eignet sich gut als Vorbereitung zur Erstellung von Studien- oder Abschlussarbeiten (Master/Diplom) im Bereich Text-Indexierung.

• 15.10.2013: Tries
• 22.10.2013: Linear Time Construction of Suffix Arrays
• 29.10.2013: Searching in Suffix Arrays; Linear Time Construction of LCP-arrays
• 5.11.2013: Suffix Trees; Approximate Search with Suffix Arrays
• 19.11.2013: Approximate Search with Suffix Arrays (ctd.); Repeats
• 26.11.2013: Range Minimum Queries
• 28.11.2013: Lempel-Ziv compression
• 3.12.2013: Lempel-Ziv compression (ctd.), Colored Range Queries and Document Retrieval
• 17.12.2013: Burrows-Wheeler-Transformation
• 7.1.2014: Backwards Search and FM-Indices
• 14.1.2014: Wavelet Trees
• 21.1.2014: Compressed Suffix Trees [slides pdf] [Arbeitsblatt pdf]
• 28.1.2014: Inverted Indexes: Introduction and Fast List Intersection Algorithms
• 4.2.2014: Inverted Indexes: Approximate Queries

Version vom 21.1.2014 [pdf]

• Übungsblatt 1 [pdf], Beispieldatensatz im ASCII-Format [500kB .gz]
• Übungsblatt 2 [pdf]
• Übungsblatt 3 [pdf]
• Übungsblatt 4 [pdf]
• Übungsblatt 5 [pdf]
• Übungsblatt 6 [pdf]
• Übungsblatt 7 [pdf]
• Übungsblatt 8 [pdf]

• Vorlesung: Di 12-14 c.t. (SRG1 2.008)
• Übungsgruppe: Do 14-16 c.t. (SRG1 3.011)